package com.h2cloud.sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @Package: com.h2cloud.sort
 * @ClassName: bucketSort
 * @Author: h2cloud
 * @CreateTime: 2021/4/15 10:25 下午
 * @Description:
 */
public class bucketSort {
    public static void main(String[] args) {

        int[] ints = myArray.get(100);
        long startTime = System.currentTimeMillis();
        QuickSort(ints, 0, ints.length - 1);
        for (int i : ints) {
            System.out.print(i + "  ");
        }
        System.out.println("时间：" + (System.currentTimeMillis() - startTime + "ms"));
    }

    public static void QuickSort(int[] arr, int low, int hight) {
        if (low < hight) {
            int middle = partition(arr, low, hight);
            QuickSort(arr, low, middle - 1);
            QuickSort(arr, middle + 1, hight);
        }
    }

    private static int partition_1(int[] arr, int low, int height) {
        int pivot = arr[low];//取基准值
        int mark = low;//Mark初始化为起始下标

        for (int i = low + 1; i <= height; i++) {
            if (arr[i] < pivot) {
                //小于基准值 则mark+1，并交换位置。
                mark++;
                int p = arr[mark];
                arr[mark] = arr[i];
                arr[i] = p;
            }
        }
        //基准值与mark对应元素调换位置
        arr[low] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }

    public static int partition(int[] arr, int low, int hight) {
        int privot = arr[low]; // 以 a[low]为基准元素
        // 以基准为标准，从两边向中间找，划分成两部分
        // 左边为比基准元素小的数，右边为比基准元素大的数
        while (low < hight) {
            while (low < hight && arr[hight] >= privot)
                --hight;
            arr[low] = arr[hight];

            while (low < hight && arr[low] <= privot)
                ++low;
            arr[hight] = arr[low];
        }
        // 将基准值插入到序列中
        arr[low] = privot;
        return low; // 返回 high也行;
    }
}
